package com.nhncorp.pleiades.util;

import java.util.Hashtable;

/**
 *   This class implements a fixed size Least-Recently-Used cache.
 *   The cache has a maximum size specified when it is created. When
 *   an item is added to the cache, if the cache is already at the
 *   maximum size the least recently used item is deleted, then the
 *   new item is added. <P>
 *
 *   The only two methods that count as "using" the object (for the
 *   least-recently-used algorithm) are <CODE>add()</CODE> and
 *   <CODE>get()</CODE>. <P>
 *
 *   The items cached are refered to by keys, just like a Hashtable.
 *
 * @author Andy John
 * @version $Revision: 1.15 $
 */
public class LRUCache {

    /*
     *  Maximum allowed size of the cache.
     */
    private int maxSize;

    /*
     *  The current size of the cache.
     */
    private int currentSize;

    /*
     *  This hashtable stores all the items, and does all the searching.
     */
    private Hashtable cache;

    /*
     *  A linked list of these structs defines the ordering from
     *  newest to oldest. The nodes are stored in the hashtable, so
     *  that constant-time access can locate a node.
     */
    private class Node {
        Node prev, next;
        Object key;
        Object item;
        int size;
    }

    /*
     *  The linked list. This is ONLY for keeping an ordering. All 
     *  searching is done via the hashtable. All acceses to this linked
     *  list are constant-time.
     */
    private Node head, tail;

    /**
     *   Create a new, empty cache.
     *
     * @param maxSize
     *  The maxmimum size of the items allowed to be in the cache.
     *  Since the size of an item defaults to 1, this is normally the
     *  number of items allowed in the cache.
     *  When this limit is reached, the "oldest" items are deleted to
     *  make room for the new item, so the total size of the cache
     *  (the sum of the sizes of all the items it contains)
     *  does not exceed the specified limit.
     */
    public LRUCache(int maxSize) {
        this.maxSize = maxSize;
        clear();
    }

    /**
     *   Returns the total size of the items in the cache.
     *   If all the items were added with the default size of 1,
     *   this is the number of items in the cache.
     *
     * @return
     *  The sum of the sizes of the items in the cache.
     */
    public synchronized int getSize() {
        return currentSize;
    }

    /**
     *   Returns the maxmimum number of items allowed in the cache.
     *
     * @return
     *  The maximum number of items allowed in the cache.
     */
    public synchronized int getMaxSize() {
        return maxSize;
    }

    /**
     *   Add an object to the cache, with a default size of 1.
     *   If the cache is full, the oldest items will be deleted to make room.
     *   The item becomes the "newest" item.
     * 
     * @param key
     *   The key used to refer to the object when calling <CODE>get()</CODE>.
     * @param item
     *   The item to add to the cache.
     */ 
    public synchronized void add(Object key, Object item) {
        add(key, item , 1);
    }

    /**
     *   Add an object to the cache. 
     *   If the cache is full, the oldest items will be deleted to make room. 
     *   The item becomes the "newest" item. 
     * 
     * @param key
     *   The key used to refer to the object when calling <CODE>get()</CODE>.
     * @param item
     *   The item to add to the cache.
     * @param size
     *   How large is the object? This counts against the maximim size
     *   specified when the cache was created.
     */ 
    public synchronized void add(Object key, Object item, int size) {
        // Throw out old one if reusing a key.
        if (cache.containsKey(key))
            remove(key);
        // Keep throwing out old items to make space. Stop if empty.
        while (currentSize + size > maxSize) {
            if (!deleteLRU())
                break;
        }
        if (currentSize + size > maxSize)
            // Just not enough room.
            return;
        Node node = new Node();
        node.key = key; 
        node.item = item; 
        node.size = size;
        cache.put(key, node);
        insertNode(node);
        currentSize += size;
    }


    /**
     *   Fetch an item from the cache. Returns null if not found.
     *   The item becomes the "newest" item.
     * 
     * @param key
     *   The key used to refer to the object when <CODE>add()</CODE>
     *   was called.
     * @return
     *   The item, or null if not found.
     */
    public synchronized Object get(Object key) {
        Node node = (Node)cache.get(key);
        if (node == null)
            return null;
        deleteNode(node);
        insertNode(node); // Move to the front of the list.
        return node.item;
    } 
  
   
    /**
     *   Remove an item from the cache.
     * 
     * @param key
     *   The key used to refer to the object when <CODE>add()</CODE>
     *   was called.
     * @return
     *   The item that was removed, or null if not found.
     */ 
    public synchronized Object remove(Object key) {
        Node node = (Node)cache.remove(key);
        if (node == null)
            return null;
        deleteNode(node);
        currentSize -= node.size;
        return node.item;
    }


    /**
     *   Does the cache contain the given key?
     *
     * @param key
     *   The key used to refer to the object when <CODE>add()</CODE>
     *   was called.
     * @return
     *   true if the key was found.
     */
    public synchronized boolean containsKey(Object key) {
        return cache.containsKey(key);
    }


    /**
     *   Delete all the items from the cache.
     */
    public synchronized void clear() {
        cache = new Hashtable();
        head = tail = null;
        currentSize = 0;
    }


    /*
     *  Insert the node at the front of the linked list.
     *  This only does linked list management.
     */ 
    private void insertNode(Node node) {
        node.next = head;
        node.prev = null;
        if (head != null)
            head.prev = node;
        head = node;
        if (tail == null)
            tail = node;
    }


    /*
     *  Delete the node from anywhere in the linked list.
     *  This only does linked list management.
     */
    private void deleteNode(Node node) {
        if (node.prev != null)
            node.prev.next = node.next;
        else
            head = node.next;
        if (node.next != null)
            node.next.prev = node.prev;
        else
            tail = node.prev;
    } 

    
    /*
     *  Delete the least recently used item. This is the one at the
     *  tail of the list. Returns true if an item was deleted, 
     *  or false if the cache is empty.
     */
    private boolean deleteLRU() {
        if (tail == null)
            return false;
        currentSize -= tail.size;
        cache.remove(tail.key);
        deleteNode(tail);
        return true;
    }

    /**
     *  Returns a string describing the contents of the cache.
     */
    public synchronized String toString() {
        StringBuffer buf = new StringBuffer();
        buf.append("LRU ");
        buf.append(currentSize);
        buf.append("/");
        buf.append(maxSize);
        buf.append(" Order: ");
        Node n = head;
        while (n != null) {
            buf.append(n.key);
            if (n.next != null)
                buf.append(", ");
            n = n.next;
        }
        return buf.toString();
    }


}

